Consider a system where a prover has to authenticate to a verifier. A typical way of achieving this is by the use of public key cryptography: the prover has a private key, only known to the prover and the verifier stores the corresponding public key. The public key thus acts as verification key and the private key as proving key. Using a cryptographic authentication protocol (for example the protocols from ISO/IEC 9798-3 or ISO/IEC 9798-5) or a secure connection (set up using a key establishment protocol e.g. SSL/TLS, ISO/IEC 10117-3) the prover authenticates to the verifier.
A problem often encountered in such systems is the storage of the private key. In systems where the prover is associated with a specific user, this user often has to enter a weak secret (e.g. a password or PIN-code) as part of the authentication process to ensure proper approval by the user. There are currently several options for the system to use this weak secret:                the weak secret is sent to the verifier (e.g. over a secure connection or using some type of key wrapping mechanism). The verifier stores a database of weak secrets (in plain or protected form). The verifier performs the verification of the weak secret. Depending on the storage used, the verifier either has access to the weak secret directly or the weak secret is easy to brute force. Especially in the case of short PIN codes the number of possible PIN codes is extremely limited, allowing for a fast brute force.        A password based authentication protocol is used. Again this requires the verifier to store the weak secret for comparison.        The weak secret is used to encapsulate the private key on the prover side. Existing encapsulation mechanism (e.g. disk encryption, key wrapping) all offer key integrity. If an incorrect weak secret is entered the de-encapsulation method detects this and reports an error. This can be done directly, by a specific function of the de-encapsulation method or indirectly, by noticing that the output after de-encapsulation is not a correctly formatted private key. Clearly this creates an issue as it is possible to brute force the weak secret and hence the private key after obtaining the encapsulated private key.        
To solve the above issues, there is a need for a novel approach and device for authentication.